package 搜索算法.深度优先搜索;

import java.util.Stack;

/**
 * 非递归实现  利用栈模拟
 */
@SuppressWarnings("all")
public class 最大岛屿问题_DFS_非递归实现 {
    public static void main(String[] args) {

    }

    public static int numIslands(char[][] grid) {
        int count = 0;
        int row = grid.length;
        int col = grid[0].length;
        char[][] temp = new char[row+2][col+2];
        for(int i = 0; i < row + 2; i++) {
            temp[i][0] = '0';
            temp[i][col+1] = '0';
        }
        for(int j = 0; j < col + 2; j++) {
            temp[0][j] = '0';
            temp[row+1][j] = '0';
        }
        for(int i = 1; i <= row; i++) {
            for(int j = 1; j <= col; j++) {
                temp[i][j] = grid[i-1][j-1];
            }
        }
        boolean[][] visited = new boolean[row+2][col+2];
        Stack<int[]> stack = new Stack<>();
        for(int i = 1; i <= row; i++) {
            for(int j = 1; j <= col; j++) {
                if(visited[i][j] == false && temp[i][j] == '1') {
                    int[] pos = new int[] {i,j};
                    stack.push(pos); // 入栈
                    while(!stack.isEmpty()) { // 如果栈不空
                        int[] top = stack.pop(); // 出栈
                        visited[top[0]][top[1]] = true;
                        // 判断当前出栈的位置的上下左右是否有相连的岛屿
                        int x = top[0];
                        int y = top[1];
                        if(visited[x-1][y] == false && temp[x-1][y] == '1') {
                            // 上
                            visited[x-1][y] = true;
                            stack.push(new int[] {x-1,y});
                        }
                        if(visited[x+1][y] == false && temp[x+1][y] == '1') {
                            // 下
                            visited[x+1][y] = true;
                            stack.push(new int[] {x+1,y});
                        }
                        if(visited[x][y-1] == false && temp[x][y-1] == '1') {
                            visited[x][y-1] = true;
                            stack.push(new int[] {x,y-1});
                        }
                        if(visited[x][y+1] == false && temp[x][y+1] == '1') {
                            visited[x][y+1] = true;
                            stack.push(new int[] {x,y+1});
                        }
                    }
                    count++;
                }
            }
        }
        return count;
    }
}
